package zuosheng.day4;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * @author lj
 * @Description: 如何仅用队列结构实现栈结构？ 如何仅用栈结构实现队列结构？
 * @date 2020-11-03 15:57
 * @QQ 851477108
 */


public class StackAndQueueConvert {
    //两个队列实现栈
    public static class TwoQueuesStack{
        private static Queue<Integer> data = new LinkedList<>();
        private static Queue<Integer> help = new LinkedList<>();
        public TwoQueuesStack(){}

        //将n全部进入data中
        public void push(int n){
            data.add(n);
        }

        //出队列,数出来
        public int pop(){
            if (data.isEmpty()){
                throw new RuntimeException("Stack is empty!");
            }
            //将data中位置为1的数不进入help，其他全部进入help中
            while (data.size() > 1){
                help.add(data.poll());
            }
            //res存储data中位置为1的数，data数全部出去，data为空
            int res = data.poll();
            //交换队列对象help和data的引用
            swap();
            //实现了后进先出,位置是1的最后进入的数却是先出,符合栈的特性
            return res;
        }

        //返回队头,数不出来
        public int peek(){
            if (data.isEmpty()){
                throw new RuntimeException("Stack is empty!");
            }
            while (data.size() != 1){
                help.add(data.poll());
            }
            int res = data.poll();
            //不让res出
            help.add(res);
            swap();
            return res;
        }


        public static void swap(){
            Queue<Integer> temp = help;
            help = data;
            data = temp;
        }
    }


    //两个栈实现队列
    public static class TwoStacksQueue {

        private Stack<Integer> stackPush = new Stack<>();
        private Stack<Integer> stackPop = new Stack<>();

        public TwoStacksQueue(){}

        //所有数据先压入stackPush中
        public void push(int pushInt){
            stackPush.push(pushInt);
        }

        //实现出队列
        public int pop(){
            if (stackPop.empty() && stackPush.empty()){
                //两者都为空,队列必为空
                throw new RuntimeException("Queue is empty!");
            }
            dao();
            //pop删除后输出队列
            return stackPop.pop();
        }

        //实现返回队列头部,不出去
        public int peek(){
            if (stackPop.empty() && stackPush.empty()){
                //两者都为空,队列必为空
                throw new RuntimeException("Queue is empty!");
            }
            dao();
            //不删除输出队列
            return stackPop.peek();
        }


        //实现push要往pop压入数据,必须一次性把push中的数据全部压入
        public void dao(){
            //pop不为空,push不能压入数据
            if (!stackPop.isEmpty()){
                return;
            }
            //将push中的数据全部压入pop中
            while (!stackPush.isEmpty()){
                //stackPush.pop()是删除栈中顶部数据并输出
                //stackPop.push()是将数据压入栈顶
                stackPop.push(stackPush.pop());
            }
        }
    }
}
